package com.chenxys.algorithm.leetcode;

import com.chenxys.algorithm.common.TreeNode;

import java.util.*;

/**
 * <p>
 *      <a href="https://leetcode.cn/problems/range-sum-of-bst/description/">二叉搜索数范围和</a>
 * </p>
 *
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.leetcode
 * @date 2024/2/26 14:47
 * @Copyright ©
 */
public class LeetCode938 {
    /**
     * <p>
     *     二叉搜索数范围和,给定二叉树的根节点，给出在[low,high]范围内的所有节点的和
     * </p>
     * @param root 二叉树根节点
     * @param low 最小值
     * @param high 最大值
     * @return 位于最小值和最大值之间的元素和
     */
    public static int rangeSumBST(TreeNode root, int low, int high) {
        if (Objects.isNull(root) || low > high) {
            return -1;
        }
        List<Integer> list = getTreeNode(root);
        assert !Objects.isNull(list);
        int sum = 0;
        for (Integer integer : list) {
            if (integer >= low && integer <= high) {
                sum += integer;
            }
        }
        return sum;
    }

    private static List<Integer> getTreeNode(TreeNode root) {
        if (Objects.isNull(root)) {
            return null;
        }
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode treeNode = null;
        while (!queue.isEmpty()){
            treeNode = queue.remove();
            res.add(treeNode.getVal());
            if (!Objects.isNull(treeNode.getLeft())) queue.offer(treeNode.getLeft());
            if (!Objects.isNull(treeNode.getRight())) queue.offer(treeNode.getRight());
        }
        Collections.sort(res);
        return res;
    }

    /**
     * <p>
     *     按深度优先搜索的顺序计算范围和。记当前子树根节点为 root，分以下四种情况讨论：
     *      root节点为空-返回 0。
     *      root节点的值大于 high-由于二叉搜索树右子树上所有节点的值均大于根节点的值，即均大于 high，故无需考虑右子树，返回左子树的范围和。
     *      root节点的值小于 low-由于二叉搜索树左子树上所有节点的值均小于根节点的值，即均小于 low，故无需考虑左子树，返回右子树的范围和。
     *      root节点的值在 [low,high]范围内-此时应返回 root节点的值、左子树的范围和、右子树的范围和这三者之和。
     * </p>
     */
    public int rangeSumBSTV1(TreeNode root, int low, int high) {
        if (root == null) {
            return 0;
        }
        if (root.getVal() > high) {
            return rangeSumBST(root.getLeft(), low, high);
        }
        if (root.getVal() < low) {
            return rangeSumBST(root.getRight(), low, high);
        }
        return root.getVal() + rangeSumBST(root.getLeft(), low, high) + rangeSumBST(root.getRight(), low, high);
    }


    /**
     * <p>
     *     使用广度优先搜索的方法，用一个队列 qqq 存储需要计算的节点。每次取出队首节点时，若节点为空则跳过该节点，否则按方法一中给出的大小关系来决定加入队列的子节点。
     * </p>
     */
    public int rangeSumBSTV2(TreeNode root, int low, int high) {
        int sum = 0;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node == null) {
                continue;
            }
            if (node.getVal() > high) {
                q.offer(node.getLeft());
            } else if (node.getVal() < low) {
                q.offer(node.getRight());
            } else {
                sum += node.getVal();
                q.offer(node.getLeft());
                q.offer(node.getRight());
            }
        }
        return sum;
    }


}
